The higher a node is in an index tree, the more likely it is to be accessed. This is because data associated with lower nodes are typically accessed through at least one upper node. Thus, the manner in which the nodes, and their associated data, are linked and arranged is critical with respect to the speed and accuracy of the data access.
As illustrated in FIG. 1, a common type of indexing arrangement permits multiple (virtual) processors 10 concurrent access to an index tree in memory 20. The subject of concurrency in indexing arrangements has a long history, with many aspects of indexing discussed at length. For example, concurrency in B.sup.+ -trees has been addressed in Bayer, R., Schkolnick, M., Concurrency of operations on B-trees, Acta Informatica Vol. 9 (1977) pp 1-21; Lehman, P., Yao, S. B., Efficient Locking For Concurrent Operations On B-Trees, ACM Trans on Database Systems, Vol. 6, No. 4 (December 1981) pp. 650-670; Sagiv, Y., Concurrent Operations On B* Trees With Overtaking, Journal of Computer and System Sciences, Vol. 33, No. 2, (1986) pp. 275-296; Salzberg., B., Restructuring The Lehman-Yao Tree, Northeastern University Technical Report TR BS-85-21 (1985), Boston, Mass.; Shasha, D., Goodman, N., Concurrent Search Structure Algorithms ACM Trans. on Database Systems, Vol. 13, No. 1 (March 1988) pp. 53-90. Unfortunately, except for the last listed paper, none of these papers addresses the problem of system crashes during structure changes.
The occurrence of a system crash during a structure change can severely impede the normal use of the system. In a multiple access system, a structure change to a set of nodes in an index tree typically requires an access lock on the data associated with those nodes. This permits the system to rearrange the data and the associated linking information without losing the identity of the data, its node and/or its relation to other nodes in the index. In structures such as the B.sup.+ -tree, where all data is stored in the leaves, upper level index nodes are only written when the shape of the tree changes. It is important then that these structure changes hold only short-term locks on index nodes, i.e., prohibit reads on data for the associated node(s), to facilitate concurrent access to the leaves via the index.
If a system crash occurs while the tree is being restructured, access to the leaves that are linked to, and/or emanate from, the index nodes may be blocked. While the likelihood of this blockage problem is dependent on the point at which the crash occurred during the restructuring process, because the inaccessibility of the blocked data may be permanent, any possibility of such an occurrence is an unacceptable possibility.
In Mohan, C. and Levine, F., ARIES/IM, An Efficient And High Concurrency Index Management Method Using Write-Ahead Logging, IBM Research Report RJ 6846, (August 1989) IBM Almaden Research Center, San Jose, Calif., a solution to this crash problem is suggested. The solution employs a nodal linking technique that anticipates a system crash by logging the next steps that must be executed in the event that a system crash occurs. In this manner, the system has a record of what it is about to do next (after a crash occurs).
This technique, unfortunately, is burdensome in terms of its applicability and flexibility for various types of index trees and recovery methods.
Accordingly, there is a need for method of concurrency in an indexing arrangement that is capable of managing concurrency and recovery for a wide class of index tree structures.